package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-preorder-traversal/">二叉树的前序遍历 [简单]</a>
 * 给定根节点root，返回前序遍历
 * 提示：
 * 树中节点数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 * 进阶：使用迭代，不使用递归
 *
 * @author zhenzicheng
 * @date 2022-06-04 13:48
 */
public class BinaryTreePreorderTravesal_144 {

  /**
   * 使用递归
   */
  // public List<Integer> preorderTraversal(TreeNode root) {
  //   List<Integer> res = new ArrayList<>();
  //   accessTree(root, res);
  //
  //   return res;
  // }

  // public void accessTree(TreeNode root, List<Integer> res) {
  //   if (root == null) {
  //     return;
  //   }
  //   res.add(root.val); // 先保存
  //   accessTree(root.left, res); // 然后访问左子树
  //   accessTree(root.right, res);
  // }
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;

    while (cur != null || !stack.isEmpty()) {
      while (cur != null) {
        res.add(cur.val);
        stack.push(cur);
        cur = cur.left;
      }
      cur = stack.pop();
      cur = cur.right;

    }

    return res;
  }

}
